﻿// 0830train02.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <algorithm>
#include <limits>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <deque>

using namespace std;

/*
 输出描述
输出查询节点的所有下层节点。以字典序排序


输入
5
b a
c a
d c
e c
f d
c

输出
d
e
f
 */
class Solution01
{
public:
    Solution01(vector<vector<string>>&pair_vec, string&search_node)
    {
        //child root
        for (auto&p_item:pair_vec)
        {
            string root = p_item[1];
            string child = p_item[0];

            linked_map[root].insert(child);
        }

        deque<string>bfs_queue;
        bfs_queue.push_back(search_node);

        vector<string>result;
        while (!bfs_queue.empty())
        {
            string top_node = bfs_queue.front();
            bfs_queue.pop_front();

            result.push_back(top_node);

            if (linked_map.count(top_node) == 0) continue;

            //子节点进bfs_queue
            for (auto&node:linked_map.at(top_node))
            {
                bfs_queue.push_back(node);
            }

            //while (!bfs_queue.empty())
        }

        result = vector<string>(result.begin() + 1, result.end());

        sort(result.begin(), result.end());

        for (auto&node:result)
        {
            cout << node << endl;
        }

        //Solution01
    }
private:
    unordered_map<string, unordered_set<string>>linked_map;
};


/*
给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的 子集（幂集）
解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列

示例 1：

输入：nums = [1,2,2]
输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]
示例 2：

输入：nums = [0]
输出：[[],[0]]
 */
class Solution02
{
public:
    
    vector<vector<int>> subsetsWithDup(vector<int>& nums) {
        //排序，相同的数排在一起，方便剪枝
        sort(nums.begin(), nums.end());
        backTrack(nums, 0);
        //cout << result.size();
        return result;
    }

    void backTrack(vector<int>& nums, int start)
    {
        result.push_back(track);

        for (int i=start; i<nums.size(); i++)
        {
            //剪枝，剪去重复的数
            if (i > start && nums[i] == nums[i - 1]) continue;
            //做选择
            track.push_back(nums[i]);
            //回溯
            backTrack(nums, i + 1);
            //撤销选择
            track.pop_back();
        }
    }
private:
    vector<vector<int>>result;
    vector<int>track;
};


/*
 返回她可以在 h 小时内吃掉所有香蕉的最小速度 k（k 为整数）。

示例 1：
输入：piles = [3,6,7,11], h = 8
输出：4

示例 2：
输入：piles = [30,11,23,4,20], h = 5
输出：30

示例 3：
输入：piles = [30,11,23,4,20], h = 6
输出：23
 */

class Solution03 {
public:
    
    int result = INT_MAX;
    long computedTime(vector<int>& piles, int speed)
    {
        if (speed == 0) return INT_MAX;
        long total_time = 0;
        for (auto&num:piles)
        {
            total_time += ceil(double(num) / double(speed));
        }
        return total_time;
    }

    int minEatingSpeed(vector<int>& piles, int h) {
        sort(piles.begin(), piles.end());

        int left = 0, right = piles[piles.size() - 1]+1; //+1保证可以取到数组中最大的数

        while (left<right)
        {
            int mid = left + (right - left) / 2;

            if (computedTime(piles, mid)<=h)
            {
                //满足条件，减小速度
                right = mid;
                result = min(result, right);
            }
            else
            {
                //大于，不满足，增大速度
                left = mid + 1;
            }

            //while (left<right)
        }



        return result;
        //minEatingSpeed
    }
};

int main()
{
	{
        Solution03 solu;
        //piles = [30,11,23,4,20], h = 5
        //piles = [3,6,7,11], h = 8
        vector<int>piles = { 30,11,23,4,20 };
        int h = 5;

        cout << solu.minEatingSpeed(piles, h);

        return 0;
	}
	{
        vector<int>nums = { 1,2,2 };
        Solution02 solu;
        solu.subsetsWithDup(nums);

        return 0;
	}
/*
5
b a
c a
d c
e c
f d
c
*/
    int v_size;
    cin >> v_size;
    cin.ignore();
    vector<vector<string>>pair_vec;

    for (int i=0; i<v_size; i++)
    {
        string input;
        getline(cin, input);
        stringstream oh_sstream(input);
        string token;

        vector<string>mini_pair;
        while (oh_sstream>>token)
        {
            mini_pair.push_back(token);
        }
        pair_vec.push_back(mini_pair);
    }

    string search_node;
    getline(cin, search_node);

    Solution01 solu(pair_vec, search_node);

}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
